# -*- coding: utf-8 -*- 
# @project : 《动态规划专题》
# @Author : created by bensonrachel on 2021/7/19
# @File : 动态规划DP专题—《最大子序列交替和》.py
# https://leetcode-cn.com/problems/maximum-alternating-subsequence-sum/

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        odd = [0] * (len(nums))
        even = [0] * (len(nums))
        # 辅助DP数组：为什么是两个呢？你就看到多了奇偶性就行了，以后就要就想到用两个DP了。其实这里也叫二维DP。
        # odd[i]代表nums中前i个（0到i-1）（两边都取闭区间）里面选择元素组成的子序列最后下标为奇数（也就是子序列长度为偶数）的最大交替和
        # even[i]代表nums中前i个里面选择元素的最后下标为偶数（也就是子序列的长度为奇数）的最大交替和

        odd[0] = 0
        even[0] = nums[0]
        # 初始值：odd的初始值肯定是0，因为肯定一个也不选，没有嘛
        #       even的初始值就是选一个（奇数个）嘛，最后的下标为0（偶数）
        for i in range(1, len(nums)):
            odd[i] = max(even[i - 1] - nums[i], odd[i - 1])
            even[i] = max(odd[i - 1] + nums[i], even[i - 1])
            # 遍历数组nums，对于每个nums[i],有选和不选两个选择，看哪个大就是哪个更新这两个dp数组。
            # 如果选了之后子序列最后的下表为奇数，就是要减去这个值，那用什么减呢，那就是用没有这个数的时候的最大交替和去减，那没有这个数的时候这个最大交替和保存在哪个数组呢，是even数组，因为没有这个数的时候最后的下标为偶数，所以要用even[i-1]去减。
            # 如果不选，那就是没有这个数进入子序列，那odd的更新只能是上一次的最后的下标为odd的值，因为这一次还是以奇数结尾，也就是odd[i-1] ,even的更新也是同理。

            # 如果选了之后下标为偶数，那就要更新even数组咯。就是要加上这个值，那用什么加呢？那就是用没有这个数的时候的最大交替和去加，那就是odd[i-1]，因为没有这个数的时候的子序列的最后下标为奇数。

            # 题目说是求最大交替和，那就是其实是在子序列中遇到偶数位（子序列的偶数位）就+，遇到奇数位（子序列的奇数位）就- 。
        return even[-1]
        # 最后，有着最大交替和的子序列的最后下标绝不可能是奇数，因为奇数位就要减，所以最大交替和肯定保存在even数组的最后一个。

        # 其实看完之后发现，每次更新（状态转移）都是只依赖于上一次的值，所以可以用两个变量代替两个数组，节省空间复杂度











